/* Copyright (C) 2010  Romolo Camplani, Marco Fortunato, Marco Marelli, Guido Rota, Fabio A. Schreiber et al.
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
 */

package org.dei.perla.sys.hlqexecutor.datastructures;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.NoSuchElementException;




/**
 * Permette la realizzazione di una struttura dati albero n-ario. 
 * Un albero è visto come un nodo che ha un nodo padre e n-sottoalberi. Ogni sottoalbero è sostanzialmente un albero.
 * Anche le foglie dell'albero sono pensata come alberi i cui sottoalberi sono nulli.
 * @author  Luigi Rinaldi
 */

public class Tree<T>{
	
	private Node<T> rootNode;
	private Node<T> nullNode = null;
	
	/**
	 * Costruttore
	 * @param node un oggetto node che rappresenterà la radice dell'albero.
	 */
	public Tree(Node<T> node) {
		this.rootNode = node;
		this.rootNode.setParent(nullNode);
	}
	
	/**
	 * Costruttore
	 * Genera un albero costituito da un solo nodo.
	 * @param obj l'oggetto generic T da memorizzare nel nodo.
	 */
	public Tree(T obj) {
		this.rootNode = new Node<T>(obj);
		this.rootNode.setParent(nullNode);
	}
	
	/**
	 * Costruttore
	 * Genera un albero constituito da un nodo che ha n-sottoalberi.
	 * @param obj obj l'oggetto generic T da memorizzare nel nodo.
	 * @param subTree n oggetti di tipo Tree da memorizzare come sottoalberi.
	 * @throws TreeException genera un'eccezzione se un subTree non è un albero valido.
	 */
	public Tree(T obj, Tree<T>... subTree) throws TreeException {
		this.rootNode = new Node<T>(obj);
		for(Tree<T> t:subTree){
			addSubTree(t);
		}
	}
	
	/**
	 * Costruttore
	 * Genera un albero constituito da un nodo che ha n-sottoalberi.
	 * @param obj obj l'oggetto generic T da memorizzare nel nodo.
	 * @param subTree un ArrayList di oggetti Tree da memorizzare come sottoalberi.
	 * @throws TreeException genera un'eccezzione se un subTree non è un albero valido.
	 */
	public Tree(T obj, ArrayList<Tree<T>> subTree) throws TreeException {
		this.rootNode = new Node<T>(obj);
		for(Tree<T> t:subTree){
			addSubTree(t);
		}
	}

	/**
	 * Permette di aggiungere un sott'albero all'albero. Il sottoalbero aggiunto è una copia.
	 * @param subTree l'oggetto TreeQuery da impostare come sott'albero.
	 * @throws TreeException lancia un'eccezzione se il sott'albero passato è gia presente
	 * nella struttura ad albero o se è già un sottoalbero di un nodo.
	 */
	public boolean addSubTree( Tree<T> subTree) throws TreeException {
		if(subTree == null)
			return false;
		if(this.contains(subTree)) throw new TreeException("The tree is already subTree");
		
		Tree<T> st = subTree.clone();
		boolean tmp = this.rootNode.addChild(st.getRootNode());
		if (tmp)
			st.getRootNode().setParent(this.getRootNode());
		return tmp;
    }
	
	/**
	 * Rimuove un sott'albero dall'albero.
	 * @param subTree l'oggetto TreeQuery da rimuovere dall'albero.
	 * @throws TreeException lancia un'eccezzione se il sott'albero passato non è presente
	 * nella struttura ad albero.
	 */
    public boolean removeSubTree(Tree<T> subTree) throws TreeException{
    	if(!contains(subTree)) throw new TreeException("The subTree isn't a subTree of this tree.");
    	
    	boolean tmp = false;
    	Node<T> del = null;
    	for(Node<T> n : this.rootNode.getChildren())
    		if(n.equals(subTree.getRootNode()))
    			del = n;		
    	tmp = this.rootNode.removeChild(del);
    	
    	return tmp;
    }
    
    /**
     * Restituisce una copia dei sottoalberi dell'albero anche nel caso in cui dovesse trattarsi di un nodo foglia.
     * @return un ArrayList di sottoalberi di tipo Tree.
     */
    @SuppressWarnings("unchecked")
	public ArrayList<Tree<T>> getSubTree() {
    	ArrayList<Tree<T>> tmp = new ArrayList<Tree<T>>();
    	for(Node<T> subTree : rootNode.getChildren()) {
    		tmp.add(new Tree(subTree.clone()));
    	}
    	return tmp;
	}
    
    /**
     * Restituisce un iteratore di sottoalberi del nodo corrente.
     * @return un oggetto Iterator di sottoalberi.
     */
    public Iterator<Tree<T>> getSubTreeIterator() {
    	return this.getSubTree().iterator();
	}
    /**
     * Restituisce il nodo radice dell'albero
     * @return un oggetto Node
     */
    public Node<T> getRootNode() {
    	return this.rootNode;
    }
    
    /**
     * Verifica se un sott'albero fa parte dell'albero o a liminte se si 
     * tratta delle stesso albero.
     * @param subTree l'oggetto TreeQuery di cui si vuol verificare la presenza.
     * @return un valore boolean che è vero se il subTree è stato trovato.
     */
    public boolean contains(Tree<T> subTree) {
    	if(subTree == null)
    		return false;
    	if(this.equals(subTree))
    		return true;
    	for (Tree<T> st:this.getSubTree())
    		if (st.contains(subTree))
    			return true;
    	return false; 
    	
    }
    
    /**
     * Permette di avere una lista di nodi foglia dell'albero.
     * @return un oggetto ArrayList di Node che rappresentano le foglie dell'albero.
     */
    public ArrayList<Node<T>> getLeaf() {
    	ArrayList<Node<T>> tmp = new ArrayList<Node<T>>();
    	if (this.rootNode.isLeaf())
    		tmp.add(this.rootNode);
    	else
    		for(Tree<T> subTree : this.getSubTree())
    			tmp.addAll(subTree.getLeaf());
    	return tmp;
    }
		
	/**
	 * Permette di iterare su un albero. Ritorna gli oggetti contenuti nei nodi dell'albero ordinati per livelli, a partire 
	 * dalle foglie fino ad arrivare al nodo radice. Riordina l'albero rispettando una sorta di dipendenza dati.
	 * @return un iteratore di oggetti generic T.
	 */
	public Iterator<Node<T>> nodeIterator() {
		return new TreeIterator<T>(this.clone());
	}

	/**
	 * Crea una copia esatta dell'oggetto tree. Ovviamente anche i nodi sono una copia.
	 * @return una copia dell'oggetto Tree.
	 */
	public Tree<T> clone() { 
		Tree<T> tmp = new Tree<T> (this.rootNode.getObject());
		try {
			for(Tree<T> st : this.getSubTree())
				tmp.addSubTree(st.clone());
		} catch (TreeException e) {
			e.printStackTrace();
			return null;
		}
		return tmp;
	}
	
	
	@SuppressWarnings("unchecked")
	@Override
	public boolean equals(Object otherObject) {
		if (this == otherObject)
			return true;
		
		if (this == null)
			return false;
		
		if (getClass() != otherObject.getClass())
			return false;
		
		Tree<T> other = (Tree<T>) otherObject; 
		
		
		if (!this.rootNode.equals(other.getRootNode()))
			return false;
		
		ArrayList<Tree<T>> a = this.getSubTree();
		ArrayList<Tree<T>> b = other.getSubTree();
		
		if (a.size() == b.size()) {
			for(int i=0; i<a.size(); i++)
				if(!a.equals(b))
					return false;
		}
		else
			return false;
		
		return true;
	}
	
	
	/**
	 * Costruisce un iteratore che itera l'albero restituento ad ogni passo dell'terazione l'informazione contenuta nei nodi dell'albero.
	 * L'ordine in cui viene restituito l'insieme degli oggetti contenuti nell'albero è il seguente: restituisce gli oggetti in modo da 
	 * rispettare le dipendenze dati imposte dall'albero, ossia restituisce prima tutte le foglie, poi tutti padri delle foglie e 
	 * cosi via dicendo.
	 * @author  Luigi Rinaldi
	 */
	private static class TreeIterator<T> implements Iterator<Node<T>> {
		private int current;
		private Node<T> tmp;
		private ArrayList<Node<T>> listNode;
		
		/**
		 * Costruttore
		 * @param tree un oggetto Tree rappresentante l'albero da iterare.
		 */
		TreeIterator(Tree<T> tree){
			listNode = new ArrayList<Node<T>>();
			current = 0;
			buildArray(tree);
		}
		
		/**
		 * Riempie ArratList listNode con tutti gli oggetti contenuti all'interno dell'albero.
		 * La particolarità sta nel fatto che ordina gli oggetti negli array rispettando le dipendeze 
		 * dei vari nodi, ossia li ordina per livello a partire dalle foglie fino ad arrivare al 
		 * nodo radice. L'albero deve essere visto come una sorta di dipendenze dati a partire dal
		 * nodo radice. Le dipendenze dati sono nulle nelle foglie.
		 * @param tree un oggetto Tree.
		 */
		private void buildArray(Tree<T> tree) {
			if(tree == null)
				return;
			else {
				for(Tree<T> subTree : tree.getSubTree()) {
					listNode.add(subTree.getRootNode());
					try {
						tree.removeSubTree(subTree);
					} catch (TreeException e) {
						e.printStackTrace();
					}
				}
				buildArray(tree);
			}
		}
		
		@Override
		public boolean hasNext() {
			return current+1==listNode.size();
		}

		@Override
		public Node<T> next() throws NoSuchElementException {
			if(!this.hasNext()) throw new NoSuchElementException("No element found");
			
			tmp = listNode.get(current);
			current++;
			return tmp;
		}

		@Override
		public void remove() {
			// TODO Non è necessario per il momento
		}
	}
}
